#include <stdio.h>
#include <stdlib.h>                         //malloc() 需要 stdlib.h 库
#include "../../include/type_list.h"
#include "../common/func.h"

// L 为带头结点的单链表的头指针，指向头结点
// 当第 i 个元素存在时，其值赋给 e 并返回 0K，否则返回 ERROR
Status GetElem_L (LinkList L, int i, ElemType & e){

    LNode * p = L -> next; 
    int j = 1;                              //初始化，p 指向第一个结点，j 为计数器

    while (p && j < i){                     //顺指针向后查找，直到 p 指向第 1 个元素或 p 为空
        p = p -> next;
        ++j;
    }

    if (! p || j > i)                       //j = 1 <= i 才是合法的，如果 p 是空的则 
        return ERROR;                       //第 1 个元素不存在
    
    e = p -> data;                          //取第 i 个元素的 data 赋值给 e
    
    return OK;

}// Getelem. L

Status ListInsert_L (LinkList & L, int i, ElemType e){

    //在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e
    LinkList p = L; 
    int j = 0;

    while (p && j < i - 1 ) { //当 j = i - 2 时，j < i - 1，此时 p = i - 2 的 next = p -> next，指向了 i - 1
        p = p -> next; 
        ++ j; 
    } //寻找第 i-1 个结点

    if (! p || j > i - 1) return ERROR;     //若 p 是 NULL (即 L 是 NULL) 则不合法  //若 j > i - 1，j 最小为 0，即 i - 1 < 0，i < 1 不合法

    LinkList s = (LinkList) malloc (sizeof (LNode)); //生成新结点 
    s -> data = e; 
    s -> next = p -> next;                  //将之前第 i 个节点的地址（即 i - 1 的 next) 赋值给新结点 s -> next
    p -> next = s;                          //设置第 i - 1 个结点的 next 指向 s

    return OK;
}// Listinsert L

Status ListDelete_L (LinkList & L, int i, ElemType & e){
    //在带头结点的单链线性表 L 中，删除第 i 个元素，并由 e 返回其值
    LinkList p = L;
    int j = 0;
                                            //寻找第 i 个结点，并令 p 指向其前趋
    while (p -> next && j < i - 1){         //判断条件和 ListInsert_L() 不同： p -> next && j < i - 1 变为了 p && j < i - 1
        p = p -> next;
        ++ j;
    }

    if (!(p -> next) || j > i - 1)          //此时 p 是第 i - 1，则 p -> next 指向第 i 个元素 （next 在 p 里边）
        return ERROR;                       //删除位置不合理 
    
    LinkList q = p -> next;                 //将 第 第 i - 1 个结点的 next (即第 i 个结点的地址) 赋值给 q
    p -> next = q -> next;                  //将 第 i 个结点的地址 (即 q) 的 next 赋值给第 i - 1 个结点的 next (即 p -> next)
    e = q -> data;                          //将原先第 i 个结点的 data 赋值给 e

    free (q);

    return OK;
}// Listdelete_L
